import java.util.*;
/*class TreeNode {
    int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
       this.val = val;
   }
 }

class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        TreeNode head = pRoot;
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        if(head == null)
            //如果是空，则直接返回空list
            return res;
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        //放入第一次
        s1.push(head);
        while(!s1.isEmpty() || !s2.isEmpty()){
            ArrayList<Integer> temp = new ArrayList<Integer>();
            //遍历奇数层
            while(!s1.isEmpty()){
                TreeNode node = s1.pop();
                //记录奇数层
                temp.add(node.val);
                //奇数层的子节点加入偶数层
                if(node.left != null)
                    s2.push(node.left);
                if(node.right != null)
                    s2.push(node.right);
            }
            //数组不为空才添加
            if(temp.size() != 0)
                res.add(new ArrayList<Integer>(temp));
            //清空本层数据
            temp.clear();
            //遍历偶数层
            while(!s2.isEmpty()){
                TreeNode node = s2.pop();
                //记录偶数层
                temp.add(node.val);
                //偶数层的子节点加入奇数层
                if(node.right != null)
                    s1.push(node.right);
                if(node.left != null)
                    s1.push(node.left);
            }
            //数组不为空才添加
            if(temp.size() != 0)
                res.add(new ArrayList<Integer>(temp));
            //清空本层数据
            temp.clear();
        }
        return res;
    }*/



import java.util.*;
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        //空节点找不到路径
        if(root == null)
            return false;
        //叶子节点，且路径和为sum
        if(root.left == null && root.right == null && sum - root.val == 0)
            return true;
        //递归进入子节点
        return hasPathSum(root.left, sum - root.val)
                || hasPathSum(root.right, sum - root.val);
    }
    boolean hasPathSum2(TreeNode root, int sum) {
        if (root == null)
            return false;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);//根节点入栈
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();//出栈
            //累加到叶子节点之后，结果等于sum，说明存在这样的一条路径
            if (cur.left == null && cur.right == null) {
                if (cur.val == sum)
                    return true;
            }
            //右子节点累加，然后入栈
            if (cur.right != null) {
                cur.right.val = cur.val + cur.right.val;
                stack.push(cur.right);
            }
            //左子节点累加，然后入栈
            if (cur.left != null) {
                cur.left.val = cur.val + cur.left.val;
                stack.push(cur.left);
            }
        }
        return false;
    }
}